#ifndef CARP_SOLUTION_H
#define CARP_SOLUTION_H

#include <bits/stdc++.h>

using namespace std;

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
  public:

    ListNode* CreateLinkList(std::vector<int> nums) {
        ListNode* head = nullptr;  // 头指针
        ListNode* current = nullptr;  // 当前指针

        for (int num : nums) {
            if (head == nullptr) {
                // 如果链表为空，创建头节点
                head = new ListNode(num);
                current = head;
            } else {
                // 否则，在当前节点后面创建新节点
                current->next = new ListNode(num);
                current = current->next;
            }
        }

        return head;  // 返回链表的头指针
    }

    ListNode* reverseKGroup(ListNode* head, int k) {

        ListNode* tail = head;

        for(int i = 0; i < k; i++) {
            if(tail == NULL) {
                return head;
            }
            tail = tail->next;
        }

        ListNode* pre = NULL;
        ListNode* cur = head;

        while(cur != tail) {
            ListNode* temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }

        head->next = reverseKGroup(tail, k);
        return pre;

    }

    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        // write code here
        if(pHead1 == NULL) {
            return pHead2;
        } else if(pHead2 == NULL) {
            return pHead1;
        }
        
        ListNode* head;
        ListNode* cur;

        if(pHead1->val <= pHead2->val) {
            head = pHead1;
            cur = head;
            pHead1 = pHead1->next;
        } else {
            head = pHead2;
            cur = head;
            pHead2 = pHead2->next;
        }

        while(pHead1 != NULL && pHead2 != NULL) {
            if(pHead1->val <= pHead2->val) {
                cur->next = pHead1;
                cur = pHead1;
                pHead1 = pHead1->next;
            } else {
                cur->next = pHead2;
                cur = pHead2;
                pHead2 = pHead2->next;
            }
        }

        if(pHead1 == NULL) {
            cur->next = pHead2;
        } else {
            cur->next = pHead1;
        }

        return head;
    }

    bool hasCycle(ListNode *head) {
        ListNode *p1 = head;
        ListNode *p2 = head;

        while(p1 != NULL && p1->next != NULL) {

            p1 = p1->next->next;

            p2 = p2->next;

            if(p1 == p2) {
                return true;
            }
        }

        return false;
    }

    ListNode* FindKthToTail(ListNode* pHead, int k) {

        int i = 0;
        ListNode* p = pHead;
        while(pHead != NULL) {
            if(i >= k) {
                p = p->next;
            }
            i++;
            pHead = pHead->next;
        }

        if(i < k) {
            return NULL;
        }

        return p;

    }

    ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
        ListNode* p1 = pHead1;
        ListNode* p2 = pHead2;

        while(p1 != NULL) {
            p2 = pHead2;
            while (p2 != NULL) {
                if(p1 == p2) {
                    return p1;
                }
                p2 = p2->next;
            }
            p1 = p1->next;
        }

        return NULL;
    }

    bool isPail(ListNode* head) {
        vector<int> nums;

        ListNode* p = head;
        while (p) {
            nums.push_back(p->val);
            p = p->next;
        }
        int n = nums.size();
        for(int i=0, j = n-1; i < n/2; i++,j--) {
            if(nums[i] != nums[j]) {
                return false;
            }
        }

        return true;
    }

    void PrintLinkList(ListNode* head) {
        while(head != NULL) {
            std::cout << head->val << " ";
            head = head->next;
        }
        std::cout << std::endl;
    }

    vector<int> preorderTraversal(TreeNode* root) {
        // write code here
    }

};

#endif